package 力扣日常刷题.木22二月.第22天228;

/**
 * @author 帅小伙
 * @date 2022/2/28
 * @description
 * https://leetcode-cn.com/problems/longest-valid-parentheses/solution/zui-chang-you-xiao-gua-hao-by-leetcode-solution/
 */
public class Demo177最长有效括号 {

    public int longestValidParentheses(String s) {
        int ans = 0;
        int[] dp = new int[s.length()];

        for (int i = 1; i <s.length(); i++) {
            if(s.charAt(i) == ')'){
                if(s.charAt(i - 1) == '('){
                    dp[i] = (i >= 2? dp[i - 2] : 0)+2;
                }else if(i - dp[i - 1] > 0 && s.charAt(i - dp[i - 1] -1) == '('){
                    dp[i] = dp[i - 1] +((i - dp[i - 1])>=2 ? dp[i - dp[i - 1] - 2]:0) + 2;
                }
            }
            ans = Math.max(ans,dp[i]);
        }
        return ans;
    }

}
